package com.leetcode.partition2;

import java.io.*;
import java.util.*;

/**
 * 127.单词接龙 启发式搜索 A Star解法
 * @author `RKC`
 * @date 2021/12/30 14:40
 */
@SuppressWarnings("all")
public class LC127单词接龙AStar {

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        List<String> wordList = new ArrayList<>();
        for (int i = 0; i < s.length; i++) wordList.add(s[i]);
        s = reader.readLine().split("\\s+");
        writer.write(ladderLength(s[0], s[1], wordList) + "\n");
        writer.flush();
    }

    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordDict = new HashSet<>(wordList);
        if (!wordDict.contains(endWord)) return 0;
        Map<String, Integer> distMap = new HashMap<>();
        PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.val, o2.val));
        distMap.put(beginWord, 1);
        heap.add(new Node(eval(beginWord, endWord), beginWord));
        while (!heap.isEmpty()) {
            Node curr = heap.poll();
            int dis = distMap.get(curr.state);
            if (curr.state.equals(endWord)) return dis;
            //对每个字符进行替换
            char[] currState = curr.state.toCharArray();
            for (int i = 0; i < currState.length; i++) {
                for (char j = 'a'; j <= 'z'; j++) {
                    char ch = currState[i];
                    currState[i] = j;
                    String next = new String(currState);
                    if (wordDict.contains(next)) {
                        if (!distMap.containsKey(next) || distMap.get(next) > dis + 1) {
                            heap.add(new Node(eval(next, endWord) + dis + 1, next));
                            distMap.put(next, dis + 1);
                        }
                    }
                    currState[i] = ch;
                }
            }
        }
        return 0;
    }

    private static int eval(String state, String target) {
        //估值函数，这里用不同的字符数作为估值
        int res = 0;
        for (int i = 0; i < state.length(); i++) {
            if (state.charAt(i) != target.charAt(i)) res++;
        }
        return res;
    }

    private static class Node {
        private int val;
        private String state;

        public Node(int val, String state) {
            this.val = val;
            this.state = state;
        }
    }
}
